//题目要求：
// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
// 你可以按任意顺序返回答案。

// 示例 1：
//     输入：nums = [2,7,11,15], target = 9
//     输出：[0,1]
//     解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
// 示例 2：
//     输入：nums = [3,2,4], target = 6
//     输出：[1,2]
// 示例 3：
//     输入：nums = [3,3], target = 6
//     输出：[0,1]
//  
// 提示：
// 2 <= nums.length <= 104
// -109 <= nums[i] <= 109
// -109 <= target <= 109
// 只会存在一个有效答案
// 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？


// #include<stdio.h>
// #include<stdlib.h>


// 方法一：暴力枚举法
// int* twoSum(int* nums,int numsSize,int target,int* returnSize)
// {
//     for(int i=0;i<numsSize;i++)
//     {
//         for(int j=i+1;j<numsSize;j++)
//         {
//             if((*(nums+i)+*(nums+j)) == target)
//             {
//                 int* ret = malloc(sizeof(int)*2);
//                 *ret = i;
//                 *(ret+1) = j;
//                 *returnSize = 2;
//                 return ret;
//             }
//         }
//     }
//     *returnSize = 0;
//     return NULL;
// }

// int main()
// {
//     int nums[] = {3,2,4};
//     int numsSize = sizeof(nums)/sizeof(nums[0]);
//     int target = 6;
//     int returnSize = 0;
//     int* results;
//     results = twoSum(nums,numsSize,target,&returnSize);
//     if(results!=NULL)
//     {
//         printf("[%d,%d]\n",*results,*(results+1));
//     }
//     else
//     {
//         printf("找不到两数之和为%d\n",target);
//     }
    
//     return 0;
// }


//方法二：使用哈希表
#include<stdio.h>
#include"uthash.h"

struct hashTable
{
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey)
{
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable,&ikey,tmp);
    return tmp;
}

void insert(int ikey,int ival)
{
    struct hashTable* it = find(ikey);
    if(it == NULL)
    {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey;
        tmp->val = ival;
        HASH_ADD_INT(hashtable,key,tmp);
    }
    else
    {
        it->val = ival;
    }
}

int* twoSum(int* nums,int numSize,int target,int* returnSize)
{
    hashtable = NULL;
    for(int i=0;i<numSize;i++)
    {
        struct hashTable* it = find(target-nums[i]);
        if(it != NULL)
        {
            int* ret = malloc(sizeof(int)*2);
            ret[0] = it->val;
            ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i],i);
    }
    *returnSize = 0;
    return NULL;
}

int main()
{
    int nums[] = {2,7,11,15};
    int target = 22;
    int numSize = sizeof(nums)/sizeof(nums[0]);
    int* returnSize;
    int* results;
    results = twoSum(nums,numSize,target,returnSize);
    if(results != NULL)
    {
        printf("[%d,%d]\n",*results,*(results+1));
    }
    else
    {
        printf("找不到两数之和为%d\n",target);
    }

    return 0;
}